{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# treelib笔记\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Node(tag=root, identifier=Root, data=2)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from treelib import Tree,Node\n",
    "import copy\n",
    "# 实例化\n",
    "tree = Tree()\n",
    "\n",
    "# 添加节点\n",
    "# tag:标签 identifier:标识 parent:父节点 data:数据\n",
    "tree.create_node(\"root\",\"Root\", parent=None, data = 2) # 根节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## tag和identifier的区别"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root\n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree.get_node(\"Root\")\n",
    "# show()的是tag\n",
    "tree.show()\n",
    "\n",
    "# get_node() 是找的identifier\n",
    "tree.get_node(\"Root\") # 可以找到Root \n",
    "tree.get_node(\"root\") # 找不到root, 因为不是identifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### tag可以重复, identifier不可以重复"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root\n",
      "└── Root\n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree= Tree()\n",
    "tree.create_node(\"root\", \"root\", data=1)\n",
    "tree.create_node(\"Root\", \"Root\", parent = \"root\", data=2)\n",
    "\n",
    "# # 报错\n",
    "# tree.create_node(\"root\", \"root2\", parent = \"root\", data=2)\n",
    "\n",
    "tree.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 获取节点数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.get_node(\"Root\").data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 展开树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "└── 3\n",
      "    ├── 4\n",
      "    └── 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree = Tree()\n",
    "tree.create_node(1, 1)  # 根节点\n",
    "tree.create_node(2, 2, parent=1)\n",
    "tree.create_node(3, 3, parent=1)\n",
    "tree.create_node(7, 7, parent=2)\n",
    "tree.create_node(6, 6, parent=2)\n",
    "tree.create_node(5, 5, parent=3)\n",
    "tree.create_node(4, 4, parent=3)\n",
    "tree.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DEPTH: [1, 2, 7, 6, 3, 5, 4]\n",
      "WIDTH: [1, 2, 3, 7, 6, 5, 4]\n",
      "ZIGZAG: [1, 3, 2, 7, 6, 5, 4]\n",
      "[1, 2, 7, 6]\n"
     ]
    }
   ],
   "source": [
    "# 返回生成器\n",
    "tree.expand_tree(mode=Tree.DEPTH)\n",
    "\n",
    "# 深度优先遍历\n",
    "print(\"DEPTH:\",[tree[node].tag for node in tree.expand_tree(mode=Tree.DEPTH, sorting=False)])\n",
    "# 广度优先遍历\n",
    "print(\"WIDTH:\",[tree[node].tag for node in tree.expand_tree(mode=Tree.WIDTH, sorting=False)])\n",
    "# 锯齿遍历\n",
    "print(\"ZIGZAG:\",[tree[node].tag for node in tree.expand_tree(mode=Tree.ZIGZAG, sorting=False)])\n",
    "\n",
    "# 自定义遍历\n",
    "print([tree[node].tag for node in tree.expand_tree(filter=lambda x: x.identifier != 3, sorting=False)])\n",
    "\n",
    "# "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 删除节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "└── 3\n",
      "    ├── 4\n",
      "    └── 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree.show()\n",
    "new_tree = copy.deepcopy(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "└── 2\n",
      "    ├── 6\n",
      "    └── 7\n",
      "\n",
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "└── 3\n",
      "    ├── 4\n",
      "    └── 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 写节点id \n",
    "new_tree.remove_node(3)\n",
    "new_tree.show()\n",
    "tree.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 移动节点\n",
    "### move_node(nid)\n",
    "移动节点 (被移动的节点, 移到哪个节点下做子节点: 如果没有就新建一个)\n",
    "\n",
    "1. 剪去一个节点\n",
    "2. 将节点加到指定节点下,如果没有就新建一个\n",
    "\n",
    "### link_past_node(nid)\n",
    "For example, if we have a -> b -> c and delete node b, we are left with a -> c."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "└── 3\n",
      "    ├── 4\n",
      "    └── 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "move_tree = copy.deepcopy(tree)\n",
    "tree.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "└── 3\n",
      "    ├── 4\n",
      "    └── 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 移动节点 (被移动的节点, 移到哪个节点下做子节点)\n",
    "# move_tree.move_node(3,6) # 返回删除的子节点个数\n",
    "# move_tree.remove_subtree(self, nid) # 返回子树\n",
    "move_subtree = copy.deepcopy(tree)\n",
    "move_tree.get_node(3).predecessor(move_tree._identifier)\n",
    "# x = move_subtree.remove_subtree(3)\n",
    "move_tree.show()\n",
    "\n",
    "# x.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "├── 4\n",
      "└── 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# link_tree = copy.deepcopy(tree)\n",
    "link_past_tree = copy.deepcopy(tree)\n",
    "link_past_tree.link_past_node(3)\n",
    "link_past_tree.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 节点和树的深度\n",
    "\n",
    "1. 树深度直接调.depth()\n",
    "2. 节点深度从树那里取\n",
    "   tree.depth(node的identifier)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "└── 3\n",
      "    ├── 4\n",
      "    └── 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "depth_tree= copy.deepcopy(tree)\n",
    "depth_tree.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# 树深度, 0开始算\n",
    "print(depth_tree.depth())\n",
    "\n",
    "# 节点深度\n",
    "print(tree.depth(tree.get_node(3)))\n",
    "print(tree.depth(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树的路径"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "├── 2\n",
      "│   ├── 6\n",
      "│   └── 7\n",
      "└── 3\n",
      "    ├── 4\n",
      "    └── 5\n",
      "\n",
      "[[1, 2, 7], [1, 2, 6], [1, 3, 5], [1, 3, 4]]\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "'int' object is not callable",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_7572/2849550841.py\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      7\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m \u001b[1;31m# 回溯\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 9\u001b[1;33m \u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mpath_tree\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mrsearch\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m5\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_7572/2849550841.py\u001b[0m in \u001b[0;36m<listcomp>\u001b[1;34m(.0)\u001b[0m\n\u001b[0;32m      7\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m \u001b[1;31m# 回溯\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 9\u001b[1;33m \u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mpath_tree\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mrsearch\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m5\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32mD:\\ProgramData\\Anaconda3\\envs\\Target-switch\\lib\\site-packages\\treelib\\tree.py\u001b[0m in \u001b[0;36mrsearch\u001b[1;34m(self, nid, filter)\u001b[0m\n\u001b[0;32m    797\u001b[0m         \u001b[0mcurrent\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnid\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    798\u001b[0m         \u001b[1;32mwhile\u001b[0m \u001b[0mcurrent\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 799\u001b[1;33m             \u001b[1;32mif\u001b[0m \u001b[0mfilter\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mcurrent\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    800\u001b[0m                 \u001b[1;32myield\u001b[0m \u001b[0mcurrent\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    801\u001b[0m             \u001b[1;31m# subtree() hasn't update the bpointer\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: 'int' object is not callable"
     ]
    }
   ],
   "source": [
    "path_tree = copy.copy(tree)\n",
    "path_tree.show()\n",
    "\n",
    "# 到叶子节点的路径\n",
    "print(path_tree.paths_to_leaves())\n",
    "\n",
    "\n",
    "# 回溯\n",
    "[i for i in path_tree.rsearch(5,1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "cf31d7f9d6f717c446f7d24d1f5ccc01e5479aa75f9a0be0bcd2450302b7de04"
  },
  "kernelspec": {
   "display_name": "Python 3.10.0 64-bit (conda)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
